package com.zf.linkedlist;

import java.util.Stack;

/**
 * @author zf
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        HeroNode h1 = new HeroNode(1,"宋江","及时雨");
        HeroNode h2 = new HeroNode(4,"卢俊义","玉麒麟");
        HeroNode h3 = new HeroNode(3,"吴用","智多星");
        HeroNode h4 = new HeroNode(2,"林冲","豹子头");
        HeroNode h5 = new HeroNode(2,"林冲2","豹子头");

        //创建链表
        SingleLinkedList linkedList = new SingleLinkedList();
        linkedList.addByOrder(h1);
        linkedList.addByOrder(h2);
        linkedList.addByOrder(h3);
        linkedList.addByOrder(h4);
        System.out.println("原链表情况：");
        linkedList.list();
//        reversesetList(linkedList.getHead());
//        System.out.println("反转后链表情况：");
//        linkedList.list();

        //反转打印
        System.out.println("反转打印的链表，未改变链表本身结构：");
        reversesetPrint(linkedList.getHead());

//        //更新
//        System.out.println("更新后的linklist");
//        linkedList.update(h5);
//        linkedList.list();
//
//        //删除
//        linkedList.del(2);
//        System.out.println("删除后的linklist");
//        linkedList.list();

        //Test getlength
//        int length = getLength(linkedList.getHead());
//        System.out.printf("链表的长度为：%d\n",length);
//        HeroNode lastIndexNode = findLastIndexNode(linkedList.getHead(), 2);

//        System.out.println(lastIndexNode);


    }

    /**
     * 显示单链表节点的个数（如果是带头节点的链表，不统计头节点）
     * @param head
     * @return
     */
    public static int getLength(HeroNode head){
        if (head.next == null){
            return 0;
        }
        int length = 0;
        HeroNode cur = head.next;
        while (cur != null){
            length++;
            cur = cur.next;
        }
        return length;
    }

    /**
     * 思路
     * 1. 编写一个方法，接收head节点，同时接收一个index
     * 2. index 表示是倒数第index个节点
     * 3. 先把链表从头到尾遍历，得到链表的总的长度 getLength
     * 4. 得到size 后，我们从链表的第一个开始遍历 (size-index)个，就可以得到
     * 5. 如果找到了，则返回该节点，否则返回nulll
     * @param head
     * @param index
     * @return
     */
    public static HeroNode findLastIndexNode(HeroNode head, int index){
        if (head.next == null){
            return null;
        }
        //第一个遍历得到链表的长度(节点个数)
        int size = getLength(head);
        //第二次遍历  size-index 位置，就是我们倒数的第K个节点

        //先做一个index的校验
        if(index <=0 || index > size) {
            return null;
        }
        //定义给辅助变量， for 循环定位到倒数的index
        HeroNode cur = head.next;
        for(int i =0; i< size - index; i++) {
            cur = cur.next;
        }
        return cur;
    }

    /**
     * 1.先保存当前节点的下一个节点
     * 2.将cur的下一个节点指向新的链表的最前端
     * 3.让cur移动到下一个节点
     * 4.将cur.next指向reverseHead.next实现反转
     * @param head
     */
    public static void reversesetList(HeroNode head){
        //如果当前链表为空，或者只有一个节点，无需反转，直接返回
        if (head.next == null || head.next.next == null){
            return;
        }

        //定义一个辅助的指针（变量），帮助遍历原来的链表
        HeroNode cur = head.next;
        HeroNode next = null;//指向当前节点[cur]的下一个节点
        HeroNode reverseHead = new HeroNode(0,"","");
        while (cur != null){
            next = cur.next;
            cur.next = reverseHead.next;
            reverseHead.next = cur;
            cur = next;
        }
        head.next = reverseHead.next;
    }

    public static void reversesetPrint(HeroNode head){
        //如果当前链表为空，无需打印
        if (head.next == null){
            return;
        }

        //创建一个栈，将各个节点压入栈
        Stack<HeroNode> stack = new Stack<>();
        HeroNode cur = head.next;

        //将链表所有节点压入栈
        while (cur != null){
            stack.push(cur);
            cur = cur.next;
        }

        //将栈中的节点进行打印
        while (stack.size() > 0){
            System.out.println(stack.pop());
        }


    }
}

class SingleLinkedList {


    /**
     * 初始化头节点，不存放具体数据
     */

    private HeroNode head = new HeroNode(0,"", "");

    public HeroNode getHead() {
        return head;
    }

    public void setHead(HeroNode head) {
        this.head = head;
    }

    /**
     *根据排名将英雄插入到指定位置
     */
    public void addByOrder(HeroNode heroNode){
        //因为单链表，因此我们找的tmp是位于添加位置的一个节点，否则插入不了
        HeroNode tmp = head;

        //标识添加的节点是否存在，否则插入不了
        boolean flag = false;
        while (true){

            //到链尾
            if (tmp.next == null){
                break;
            }

            //位置找到，插在tmp之后
            if (tmp.next.no > heroNode.no){
                break;
            } else if (tmp.next.no == heroNode.no){
                //希望添加的heroNode已存在//说明编号存在
                flag = true;
                break;
            }
            tmp = tmp.next;
        }

        if (flag){
            System.out.printf("准备插入的英雄编号%d 已经存在，不能加入\n",heroNode.no);
        }else {
            //插入到链表中，tmp的后面
            heroNode.next = tmp.next;
            tmp.next = heroNode;
        }
    }

    public void add(HeroNode heroNode){
        //添加节点到单项链表
        //不考虑编号顺序
        //1、找到当前链表的最后节点
        //2、将最后节点的next指向新节点
        HeroNode tmp = head;
        //遍历链表找到最后
        while (true){
            //找到最后
            if (tmp.next == null){
                break;
            }
            //未找到最后
            tmp = tmp.next;
        }

        //当退出循环时，tmp指向了链表的最后,将tmp指向新节点
        tmp.next = heroNode;

    }

    /**
     * 删除节点
     * 1. head 不能动，因此我们需要一个temp辅助节点找到待删除节点的前一个节点
     * 2. 说明我们在比较时，是temp.next.no 和需要删除的节点的no比较
     */
    public void del(int no){
        HeroNode tmp = head;
        boolean flag = false;
        while (true){
            if (tmp.next == null){
                break;
            }
            if (tmp.next.no == no){
                flag = true;
                break;
            }
            tmp = tmp.next;
        }
        if (flag){
            tmp.next = tmp.next.next;
        }else {
            System.out.printf("要删除的节点%d不存在\n",no);
        }
    }

    /**
     * 显示所有节点
     */

    public void list(){
        //判断节点是否为空
        if (head.next == null){
            System.out.println("链表为空");
            return;
        }

        //利用辅助节点遍历链表
        HeroNode tmp = head.next;
        while (true){
            //判断链表是否到了最后
            if (tmp == null){
                break;
            }
            //输出节点的信息
            System.out.println(tmp);
            tmp = tmp.next;
        }
    }

    /**
     * 改
     * 根据no来修改
     * @param newHeroNode
     */
    public void update(HeroNode newHeroNode){
        if (head.next == null){
            System.out.println("链表为空");
        }
        HeroNode tmp = head.next;
        boolean flag = false;
        while (true){
            if (tmp == null){
                break;
            }
            if (tmp.no == newHeroNode.no){
                flag = true;
                break;
            }
            tmp = tmp.next;
        }

        if (flag){
            tmp.name = newHeroNode.name;
            tmp.nickname = newHeroNode.nickname;
        }else {
            System.out.printf("没有找到编号为%d的英雄",newHeroNode.no);
        }

    }

}



/**
 * 定义HeroNode，每个HeroNode就是一个节点
 */
class HeroNode {
    public int no;
    public String name;
    public String nickname;
    public HeroNode next;

    public HeroNode(int hNo, String hName, String hNickname) {
        this.no = hNo;
        this.name = hName;
        this.nickname = hNickname;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname +
                '}';
    }
}
